package gold.gold05;

/**
 *
 */
public class S1712BiNode_二叉树转链表 {
    /**
     * 82, 时间都一样, 这里用了一个自定义的Entry类来处理这种需要entry对的问题。思来想去, 这个应该也算是原址操作。
     * 即转成一个递增的链表, 中序遍历, 树的话递归吧。但是不能创建新的节点。
     */
    public TreeNode convertBiNode(TreeNode root) {
        if(root == null) return null;
        return getLeftRight(root).left;
    }

    private Entry getLeftRight(TreeNode root){
        if(root == null) return null;
        Entry leftEntry = getLeftRight(root.left);
        Entry rightEntry = getLeftRight(root.right);
        if(leftEntry == null && rightEntry == null){
            root.left = null;
            return new Entry(root, root);
        }else if(leftEntry != null && rightEntry != null){
            leftEntry.right.right = root;
            root.left = null;
            root.right = rightEntry.left;
            return new Entry(leftEntry.left, rightEntry.right);
        }else if(leftEntry != null && rightEntry == null){
            leftEntry.right.right = root;
            root.left = null;
            return new Entry(leftEntry.left, root);
        }else{
            // (leftEntry == null && rightEntry != null)
            root.left = null;
            root.right = rightEntry.left;
            return new Entry(root, rightEntry.right);
        }

    }

    private class Entry{
        public Entry(TreeNode left, TreeNode right){
            this.left = left;
            this.right = right;
        }
        public TreeNode left;
        public TreeNode right;
    }

    /**
     * 这个好诶。一定复现一下。
     */
    private TreeNode head = null;
    private TreeNode current = null;
    public TreeNode convertBiNode2(TreeNode root) {
        if (root == null) {
            return null;
        }
        travel(root);
        return head;

    }
    // 这个中序遍历很好啊, 我总是想不出来写这样的。
    // 中序遍历, 然后把每次遍历到的节点塞到之前遍历结果的头结点的前面。这样就没有上面那种需要同时返回头和尾的需求了。
    public void travel(TreeNode node) {
        if (node.left != null) {
            travel(node.left); // 这个找最小点的操作挺好的。
        }
        node.left = null;
        if (head == null) {
            head = node;
            current = node;
        } else {
            current.right = node;
            current = node;
        }
        if (node.right != null) {
            travel(node.right);
        }
    }
}

// 二叉树公用类。
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) {
        val = x;
    }
}